﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Practice14
{
    class Program
    {
        /*
        static void Main(string[] args)
        {
            Node Tree = getTree();
            Console.Write("前序遍历: ");
            preOrderTraverse(Tree);
            Console.WriteLine();
            Console.Write("中序遍历: ");
            inOrderTraverse(Tree);
            Console.WriteLine();
            Console.Write("后序遍历: ");
            postOrderTraverse(Tree);
            Console.WriteLine();
            Console.Write("前序遍历: ");
            preOrderTraverseNoRecursion(Tree);
            Console.WriteLine();
            Console.Write("中序遍历: ");
            inOrderTraverseNoRecursion(Tree);
            Console.WriteLine();
            Console.Write("后序遍历: ");
            postOrderTraverseNoRecursion(Tree);

            Console.ReadLine();
        }
        */
        static Node getTree()
        {
            return new Node("A",
                new Node("B",
                    null,
                    new Node("D",
                        new Node("G"),
                        null)
                    ),
                new Node("C",
                    new Node("E",
                        null,
                        new Node("H")
                        ),
                    new Node("F")
                    )
                );
        }

        // 前序遍历 A B D G C E H F
        static void preOrderTraverse(Node tree)
        {
            if (tree != null)
            {
                Console.Write(tree.value + " ");
                preOrderTraverse(tree.leftChild);
                preOrderTraverse(tree.rightChild);
            }
        }

        // 中序遍历 B G D A E H C F
        static void inOrderTraverse(Node tree)
        {
            if (tree != null)
            {
                inOrderTraverse(tree.leftChild);
                Console.Write(tree.value + " ");
                inOrderTraverse(tree.rightChild);
            }
        }

        // 后序遍历 G D B H E F C A
        static void postOrderTraverse(Node tree)
        {
            if (tree != null)
            {
                postOrderTraverse(tree.leftChild);
                postOrderTraverse(tree.rightChild);
                Console.Write(tree.value + " ");
            }
        }

        // 前序遍历
        static void preOrderTraverseNoRecursion(Node tree)
        {
            Stack st = new Stack();

            while (tree != null || st.Count != 0)
            {
                if (tree != null)
                {
                    Console.Write(tree.value + " ");
                    st.Push(tree);
                    tree = tree.leftChild;
                }
                else
                {
                    Node node = (Node)st.Pop();
                    tree = node.rightChild;
                }
                
            }
        }

        // 中序遍历
        static void inOrderTraverseNoRecursion(Node tree)
        {
            Stack st = new Stack();

            while (tree != null || st.Count != 0)
            {
                if(tree != null)
                {
                    st.Push(tree);
                    tree = tree.leftChild;
                }
                else
                {
                    Node node = (Node)st.Pop();
                    Console.Write(node.value + " ");
                    tree = node.rightChild;
                }
            }
        }

        // 后序遍历
        static void postOrderTraverseNoRecursion(Node tree)
        {
            Stack st = new Stack();
            List<Node> alreadyRead = new List<Node> { };

            while (tree != null || st.Count != 0)
            {
                if (tree != null)
                {
                    st.Push(tree);
                    tree = tree.leftChild;
                }
                else
                {
                    Node node1 = (Node)st.Peek();
                    if (node1.rightChild != null && !alreadyRead.Contains(node1))
                    {
                        alreadyRead.Add(node1);
                        tree = node1.rightChild;
                    }
                    else
                    {
                        Node node2 = (Node)st.Pop();
                        Console.Write(node2.value + " ");
                        if (alreadyRead.Contains(node2))
                        {
                            tree = null;
                        }
                    }
                }
            }
        }
    }
    class Node
    {
        public string value;
        public Node leftChild;
        public Node rightChild;
        public Node() { }
        public Node(string value)
        {
            this.value = value;
        }
        public Node(string value, Node leftChild, Node rightChild)
        {
            this.value = value;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
        public override string ToString()
        {
            string leftStr = leftChild == null ? "null" : leftChild.ToString();
            string rightStr = rightChild == null ? "null" : rightChild.ToString();
            return $"[Node:{value},left:{leftStr},right:{rightStr}";
        }
    }
}